#ifndef ARRAYSORT_H_
#define ARRAYSORT_H_

#include <stack>

template <typename T>
void swap(T &a, T &b) {
    T t = a;
    a = b;
    b = t;
}

template <class T>
struct less {
    bool operator()(const T &a, const T &b) const {
        return a < b;
    }
};

template <class T, class C = less<T> >
struct ISort {
    C fnComp;
    virtual void sort(T *array, int size) = 0;
};

/******************************
 * Bubble Sort                *
 ******************************/
template <class T, class C = less<T> >
class BubbleSort: public ISort<T, C> {
public:
    void sort(T *array, int size) {
        bool sw;
        for (int i = size - 1; i > 0; i--) {
            sw = false;
            for (int j = 0; j < i; j++) {
                if (fnComp(array[j+1], array[j])) {
                    swap(array[j], array[j+1]);
                    sw = true;
                }
            }
            if (!sw) {
                break;
            }
        }
    }
};

/******************************
 * Insertion Sort             *
 ******************************/
template <class T, class C = less<T> >
class InsertionSort: public ISort<T, C> {
public:
    void sort(T *array, int size) {
        int i, j;
        for (i = 1; i < size; i++) {
            T tmp = array[i];
            for (j = i - 1; j >= 0; j--) {
                if (!fnComp(tmp, array[j])) {
                    break;
                }
                /* make room */
                array[j + 1] = array[j];
            }
            /* update current */
            array[j + 1] = tmp;
        }
    }
};

/******************************
 * Shell Sort                 *
 ******************************/
template <class T, class C = less<T> >
class ShellSort: public ISort<T, C> {
public:
    void sort(T *array, int size) {
        const static int stp = 3;
        const static int gap = 9;
        int h, i, j;

        for (h = 1; h <= size / gap; h = stp * h + 1) {
            /* find starting h */
        }
        for (; h > 0; h /= stp) {
            for (i = h; i < size; i++) {
                T tmp = array[i];
                for (j = i - h; j >= 0; j -= h) {
                    if (!fnComp(tmp, array[j])) {
                        break;
                    }
                    /* make room */
                    array[j + h] = array[j];
                }
                /* update current */
                array[j + h] = tmp;
            }
        }
    }
};

/******************************
 * Heap Sort                  *
 ******************************/
template <class T, class C = less<T> >
class HeapSort: public ISort<T, C> {
private:
    int left(int i) {
        return 2 * i + 1;
    }
    void sift(T *array, int size, int index) {
        int maxChild, root;
        root = index;
        while ((maxChild = left(root)) < size) {
            if (maxChild != size - 1 && fnComp(array[maxChild], array[maxChild + 1])) {
                maxChild++;
            }
            if (fnComp(array[maxChild], array[root])) {
                break;
            } else {
                swap(array[root], array[maxChild]);
            }
            root = maxChild;
        }
    }
public:
    void sort(T *array, int size) {
        for (int i = size / 2; i >= 0; i--) {
            sift(array, size, i);
        }
        for (int i = size - 1; i > 0; i--) {
            swap(array[0], array[i]);
            sift(array, i, 0);
        }
    }
};

/******************************
 * Merge Sort                 *
 ******************************/
template <class T, class C = less<T> >
class MergeSort: public ISort<T, C> {
private:
    void merge(T *array, T *tmpArray, int left, int mid, int right) {
        int curr1 = left;
        int curr2 = mid;
        int tmpAll = left;
        while ((curr1 <= mid - 1) && (curr2 <= right)) {
            if (fnComp(array[curr1], array[curr2])) {
                tmpArray[tmpAll++] = array[curr1++];
            } else {
                tmpArray[tmpAll++] = array[curr2++];
            }
        }
        while (curr1 <= mid - 1) {
            tmpArray[tmpAll++] = array[curr1++];
        }
        while (curr2 <= right) {
            tmpArray[tmpAll++] = array[curr2++];
        }
        /* copy back */
        for (int i = left; i <= right; i++) {
            array[i] = tmpArray[i];
        }
    }
    void sort(T *array, T *tmpArray, int left, int right) {
        int mid;
        if (right > left) {
            mid = (right + left) / 2;
            sort(array, tmpArray, left, mid);
            sort(array, tmpArray, mid + 1, right);
            merge(array, tmpArray, left, mid + 1, right);
        }
    }
public:
    void sort(T *array, int size) {
        T *tmpArray = new T[size];
        sort(array, tmpArray, 0, size - 1);
        delete[] tmpArray;
    }
};

/******************************
 * Quick Sort                 *
 ******************************/
template<typename T, typename C>
T median3(T *array, C fnComp, int left, int right) {
    int mid = (left + right) / 2;
    if (fnComp(array[mid], array[left])) {
        swap(array[mid], array[left]);
    }
    if (fnComp(array[right], array[left])) {
        swap(array[right], array[left]);
    }
    if (fnComp(array[right], array[mid])) {
        swap(array[right], array[mid]);
    }
    /* get pivot */
    swap(array[mid], array[right-1]);
    return array[right-1];
}

template<class T, class C>
void insertion_sort(T *array, C fnComp, int left, int right) {
    int i, j;
    for (i = left + 1; i <= right; i++) {
        T tmp = array[i];
        for (j = i - 1; j >= 0; j--) {
            if (!fnComp(tmp, array[j])) {
                break;
            }
            /* make room */
            array[j + 1] = array[j];
        }
        /* update current */
        array[j + 1] = tmp;
    }
}

/* version 1 */
template <class T, class C = less<T> >
class QuickSort: public ISort<T, C> {
    using ISort<T, C>::fnComp;
private:
    void sort(T *array, int left, int right) {
        /* at least 10 elements */
        const static int diff = 9;
        if (right - left < diff) {
            insertion_sort(array, fnComp, left, right);
        } else {
            T pivot = median3(array, fnComp, left, right);
            int i = left;
            int j = right - 1;
            while (true) {
                while (fnComp(array[++i], pivot)) { }
                while (!fnComp(array[--j], pivot)) { }
                if (i > j) {
                    break;
                }
                swap(array[i], array[j]);
            }
            swap(array[i], array[right - 1]);
            sort(array, left, i - 1);
            sort(array, i + 1, right);
        }
    }
public:
    void sort(T *array, int size) {
        sort(array, 0, size - 1);
    }
};

/* version 2 */
template <class T, class C = less<T> >
class QuickSort2: public ISort<T, C> {
    using ISort<T, C>::fnComp;
private:
    void sort(T *array, int left, int right) {
        /* at least 10 elements */
        const static int diff = 9;
        int l = left;
        int r = right;
        while (r - l >= diff) {
            T pivot = median3(array, fnComp, left, right);
            int i = left;
            int j = right - 1;
            while (true) {
                while (fnComp(array[++i], pivot)) { }
                while (!fnComp(array[--j], pivot)) { }
                if (i > j) {
                    break;
                }
                swap(array[i], array[j]);
            }
            swap(array[i], array[right - 1]);
            /* only recurse on smaller half */
            if (i - l < r - i) {
                sort(array, l, i - 1);
                l = i + 1;
            } else {
                sort(array, i + 1, r);
                r = i - 1;
            }
        }
    }
public:
    void sort(T *array, int size) {
        sort(array, 0, size - 1);
        insertion_sort(array, fnComp, 0, size - 1);
    }
};

/* version 3 */
template <class T, class C = less<T> >
class QuickSort3: public ISort<T, C> {
    using ISort<T, C>::fnComp;
public:
    void sort(T *array, int size) {
        /* at least 10 elements */
        const static int diff = 9;
        std::stack<int> s;
        s.push(size - 1);
        s.push(0);
        while (!s.empty()) {
            int left = s.top();
            s.pop();
            int right = s.top();
            s.pop();
            if (right - left < diff) {
                insertion_sort(array, fnComp, left, right);
                continue;
            }
            int i = left;
            int j = right - 1;
            T pivot = median3(array, fnComp, left, right);
            while (true) {
                while (fnComp(array[++i], pivot)) { }
                while (!fnComp(array[--j], pivot)) { }
                if (i > j) {
                    break;
                }
                swap(array[i], array[j]);
            }
            swap(array[i], array[right - 1]);
            /* push 2 divided parts */
            s.push(right);
            s.push(i + 1);
            s.push(i - 1);
            s.push(left);
        }
    }
};

#endif /* ARRAYSORT_H_ */
